The following prior art references are considered by applicant to be the most pertinent to the present invention:
[A] U.S. Pat. No. 4,888,779, granted Dec. 19, 1989, entitled "Matched Spectral Null Trellis Codes For Partial Response Channels."
[B] U.S. Pat. No. 5,257,272, granted Oct. 26, 1993, entitled "Time-Varying Modulo N Trellis Codes For Input Restricted Partial Response Channels."
[C] U.S. Pat. No. 5,280,489, granted Jan. 18, 1994, entitled "Time-Varying viterbi Detector For Control Of Error Event Length."
[D] Commonly assigned U.S. application Ser. No. 08/174,904, filed Dec. 24, 1993 (pending), entitled "Permuted Trellis Codes For Input Restricted Partial Response Channels."
Partial response channels of interest for data storage devices include those with channel polynomials of the form P(D)=(1-D.sup.n) or (1+D.sup.n), where n is a nonnegative integer. Channels with this form have a practical implementation advantage in that they can be de-interleaved into n separate (1-D) channels or n separate (1+D) channels, respectively.
Reference [A] discloses a method for increasing the reliability of partial response storage channels by increasing the minimum distance between coded output sequences using so-called matched spectral null (MSN) trellis codes designed to match the spectral nulls in a channel partial response polynomial. The viterbi detectors in Reference [A] reduce complexity by tracking only the spectral content of detected sequences.
The "minimum distance" of a particular detector trellis (sometimes referred to in the art as d.sup.2.sub.free) is defined as the minimum sum of the squared differences between sequences of noiseless sample values resulting from two distinct paths that diverge from a common state on the trellis and remerge to a common state. For partial response, maximum likelihood (PRML) detection, the minimum distance is 2; but the first-order matched-spectral null codes of Reference [A] increase the minimum distance to 4. In order to realize the benefits of increased minimum distance in a Viterbi detector with finite path memory, it is required that any pair of sequences consisting of a coded sequence and another detector trellis sequence accumulate the distance within a finite number of samples. If the code contains "quasi-catastrophic" sequences, which are defined as sequences that are represented by more than one distinct path through the detector trellis, the minimum distance will not be accumulated in a finite number of samples, so it is necessary for the code to avoid such sequences. Reference [A] describes a method for eliminating quasi-catastrophic sequences.
Reference [B] describes a Viterbi detector which replicates a conventional trellis pattern for the desired channel N times. The N copies of the channel response trellis are interconnected in such a way that a preselected function associates each state in the trellis with a particular integer value modulo N. The number N is selected according to the channel detection and coding constraints so that diverging erroneous sequences of minimum distance lead to detector states which are distinct from the correct detector state. Only certain values of the preselected function tracked modulo N are allowed every m bits in order to increase the minimum distance between output sequences in the partial response channel and eliminate quasi-catastrophic sequences. The codes described in Reference [B] do not match the spectral nulls in the polynomial for the channel.
Reference [C] describes a Viterbi detector based upon a time-varying trellis structure for detection of codes with spectral nulls or spectral-density nulls. The trellis is obtained by selective deletion of states and edges from the trellis that tracks the spectral content of the output sequences. The time-varying structure provides for reduced error-event length by eliminating paths corresponding to certain quasi-catastrophic sequences. However, in order to maintain the desired high code rates, it was necessary to significantly increase the codeword block length or the number of trellis states, resulting in larger code and detector complexity.
Reference [D] describes sequences that are concatenated according to rules that depend upon the running digital sum (RDS) value of a sequence and that of its successor. The detector trellis structure combines subtrellises that track RDS or RDS modulo N, with reassignment of survivor metrics and survivor sequences at the subtrellis boundaries according to the sequence concatenation rules. The resulting detector trellis structure requires periodic permutation of states and hence is referred to as a "permuted trellis code." The sequences and the concatenation rules are selected to realize coding gain, eliminate quasi-catastrophic sequences from the detector trellis, limit the complexity of the maximum-likelihood detector, and improve runlength constraints relative to earlier proposed methods.
However, these references do not suggest (1) providing an encoder that imposes algebraic constraints upon a set of allowable code sequences to enable detection of specified error events; (2) providing a detector which (i) not only generates an estimate of a most probable binary sequence from a received sample, but also (ii) examines the detected sequence for violations of the algebraic constraints, and (iii) flags such violations to detect the occurrence of one of said specified error events; and (3) using an enlarged time-varying detector trellis to correct said error events.